"""
1481. 不同整数的最少数目
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。



示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。


提示：

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
"""


class Solution(object):
    def findLeastNumOfUniqueInts(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        dict = {}
        for i in arr:
            if i in dict:
                dict[i] += 1
            else:
                dict[i] = 1
        # 字典根据值进行排序
        dict = sorted(dict.items(), key=lambda x: x[1])
        res = 0
        for i in dict:
            if k >= i[1]:
                k -= i[1]
                res+=1
            else:
                break
        return len(dict) - res

if __name__ == '__main__':
    arr = [2,1,1,3,3,3]
    k = 3
    print(Solution().findLeastNumOfUniqueInts(arr,k))# 1
    l1 = [1,2,3]
    l1.pop()
    print(l1)